SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Cyclomatic complexity</title>

</head>

Cyclomatic complexity

</h1>

</header>

Cyclomatic complexity is a <a href="Software_metric" title="Software metric">software metric</a> used to indicate the <a href="Programming_complexity" title="Programming complexity">complexity of a program</a>. It is a quantitative measure of the number of linearly independent <a href="Path_(graph_theory)" title="Path (graph theory)">paths</a> through a program's <a href="Source_code" title="Source code">source code</a>. It was developed by Thomas J. McCabe, Sr. in 1976.

Cyclomatic complexity is computed using the <a href="Control-flow_graph" title="Control-flow graph">control-flow graph</a> of the program. The nodes of the <a href="Directed_graph" title="Directed graph">graph</a> correspond to indivisible groups of commands of a program, and a <a href="Directed_edge" class="mw-redirect" title="Directed edge">directed edge</a> connects two nodes if the second command might be executed immediately after the first command. Cyclomatic complexity may also be applied to individual <a href="Function_(computer_science)" class="mw-redirect" title="Function (computer science)">functions</a>, <a href="Modular_programming" title="Modular programming">modules</a>, <a href="Method_(computer_science)" class="mw-redirect" title="Method (computer science)">methods</a>, or <a href="Class_(computer_science)" class="mw-redirect" title="Class (computer science)">classes</a> within a program.

One <a href="Software_testing" title="Software testing">testing</a> strategy, called <a href="Basis_path_testing" title="Basis path testing">basis path testing</a> by McCabe who first proposed it, is to test each linearly independent path through the program. In this case, the number of test cases will equal the cyclomatic complexity of the program.<a href="#cite_note-1">[1]</a>

<div class="mw-heading mw-heading2"><h2 id="Description">Description</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Definition">Definition</h3></div>

There are multiple ways to define cyclomatic complexity of a section of <a href="Source_code" title="Source code">source code</a>. One common way is the number of linearly independent <a href="Path_(graph_theory)" title="Path (graph theory)">paths</a> within it. A set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"> of paths is linearly independent if the edge set of any path <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"> in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"> is not the union of edge sets of the paths in some subset of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S/P}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S/P}</annotation>

</semantics>

</math><img src="./9fc8844fb3e3e501c0b35e7bf91fdbc8813b98ed.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.407ex; height:2.843ex;" alt="{\displaystyle S/P}" loading="lazy">. If the source code contained no <a href="Control_flow" title="Control flow">control flow statements</a> (conditionals or decision points) the complexity would be 1, since there would be only a single path through the code. If the code had one single-condition <a href="If_statement" class="mw-redirect" title="If statement">IF statement</a>, there would be two paths through the code: one where the IF statement is TRUE and another one where it is FALSE. Here, the complexity would be 2. Two nested single-condition IFs, or one IF with two conditions, would produce a complexity of 3.

Another way to define the cyclomatic complexity of a program is to look at its <a href="Control-flow_graph" title="Control-flow graph">control-flow graph</a>, a <a href="Directed_graph" title="Directed graph">directed graph</a> containing the <a href="Basic_block" title="Basic block">basic blocks</a> of the program, with an edge between two basic blocks if control may pass from the first to the second. The complexity M is then defined as<a href="#cite_note-mccabe76-2">[2]</a>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M=E-N+2P,}</annotation>

</semantics>

</math>

where

<ul><li>E = the number of edges of the graph.</li>

<li>N = the number of nodes of the graph.</li>

<li>P = the number of <a href="Component_(graph_theory)" title="Component (graph theory)">connected components</a>.</li></ul>

An alternative formulation of this, as originally proposed, is to use a graph in which each exit point is connected back to the entry point. In this case, the graph is <a href="Strongly_connected" class="mw-redirect" title="Strongly connected">strongly connected</a>. Here, the cyclomatic complexity of the program is equal to the <a href="Cyclomatic_number" title="Cyclomatic number">cyclomatic number</a> of its graph (also known as the <a href="Betti_number#Example_2:_the_first_Betti_number_in_graph_theory" title="Betti number">first Betti number</a>), which is defined as<a href="#cite_note-mccabe76-2">[2]</a>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M=E-N+P.}</annotation>

</semantics>

</math>

This may be seen as calculating the number of <a href="Linearly_independent_cycle" class="mw-redirect" title="Linearly independent cycle">linearly independent cycles</a> that exist in the graph: those cycles that do not contain other cycles within themselves. Because each exit point loops back to the entry point, there is at least one such cycle for each exit point.

For a single program (or subroutine or method), P always equals 1; a simpler formula for a single subroutine is<a href="#cite_note-Laplante2007-3">[3]</a>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M=E-N+2.}</annotation>

</semantics>

</math>

Cyclomatic complexity may be applied to several such programs or subprograms at the same time (to all of the methods in a class, for example). In these cases, P will equal the number of programs in question, and each subprogram will appear as a disconnected subset of the graph.

McCabe showed that the cyclomatic complexity of a structured program with only one entry point and one exit point is equal to the number of decision points ("if" statements or conditional loops) contained in that program plus one. This is true only for decision points counted at the lowest, machine-level instructions.<a href="#cite_note-4">[4]</a> Decisions involving compound predicates like those found in <a href="High-level_language" class="mw-redirect" title="High-level language">high-level languages</a> like <code>IF cond1 AND cond2 THEN ...</code> should be counted in terms of predicate variables involved. In this example, one should count two decision points because at machine level it is equivalent to <code>IF cond1 THEN IF cond2 THEN ...</code>.<a href="#cite_note-mccabe76-2">[2]</a><a href="#cite_note-ecst-5">[5]</a>

Cyclomatic complexity may be extended to a program with multiple exit points. In this case, it is equal to

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \pi -s+2,}</annotation>

</semantics>

</math>

where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \pi }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \pi }</annotation>

</semantics>

</math><img src="./9be4ba0bb8df3af72e90a0535fabcc17431e540a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.332ex; height:1.676ex;" alt="{\displaystyle \pi }" loading="lazy"> is the number of decision points in the program and s is the number of exit points.<a href="#cite_note-ecst-5">[5]</a><a href="#cite_note-harrison-6">[6]</a>

<div class="mw-heading mw-heading3"><h3 id="Interpretation">Interpretation</h3></div>

In his presentation "Software Quality Metrics to Identify Risk"<a href="#cite_note-7">[7]</a> for the Department of Homeland Security, Tom McCabe introduced the following categorization of cyclomatic complexity:

<ul><li>1 - 10: Simple procedure, little risk</li>

<li>11 - 20: More complex, moderate risk</li>

<li>21 - 50: Complex, high risk</li>

<li>> 50: Untestable code, very high risk</li></ul>

<div class="mw-heading mw-heading2"><h2 id="In_algebraic_topology">In algebraic topology</h2></div>

An even subgraph of a graph (also known as an <a href="Eulerian_path" title="Eulerian path">Eulerian subgraph</a>) is one in which every <a href="Vertex_(graph_theory)" title="Vertex (graph theory)">vertex</a> is <a href="Graph_(discrete_mathematics)#Graph" title="Graph (discrete mathematics)">incident</a> with an even number of edges. Such subgraphs are unions of cycles and isolated vertices. Subgraphs will be identified with their edge sets, which is equivalent to only considering those even subgraphs which contain all vertices of the full graph.

The set of all even subgraphs of a graph is closed under <a href="Symmetric_difference" title="Symmetric difference">symmetric difference</a>, and may thus be viewed as a <a href="Vector_space" title="Vector space">vector space</a> over <a href="GF(2)" title="GF(2)">GF(2)</a>. This vector space is called the cycle space of the graph. The <a href="Cyclomatic_number" title="Cyclomatic number">cyclomatic number</a> of the graph is defined as the <a href="Dimension_(vector_space)" title="Dimension (vector space)">dimension</a> of this space. Since GF(2) has two elements and the cycle space is necessarily finite, the cyclomatic number is also equal to the <a href="Binary_logarithm" title="Binary logarithm">2-logarithm</a> of the number of elements in the cycle space.

A <a href="Basis_(linear_algebra)" title="Basis (linear algebra)">basis</a> for the cycle space is easily constructed by first fixing a <a href="Glossary_of_graph_theory#Trees" title="Glossary of graph theory">spanning forest</a> of the graph, and then considering the cycles formed by one edge not in the forest and the path in the forest connecting the endpoints of that edge. These cycles form a basis for the cycle space. The cyclomatic number also equals the number of edges not in a maximal spanning forest of a graph. Since the number of edges in a maximal spanning forest of a graph is equal to the number of vertices minus the number of components, the formula <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E-N+P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E-N+P}</annotation>

</semantics>

</math><img src="./c90a4856abe1ef57f4c28079fcd1eb7427ebcbda.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:11.265ex; height:2.343ex;" alt="{\displaystyle E-N+P}" loading="lazy"> defines the cyclomatic number.<a href="#cite_note-8">[8]</a>

Cyclomatic complexity can also be defined as a relative <a href="Betti_number" title="Betti number">Betti number</a>, the size of a <a href="Relative_homology" title="Relative homology">relative homology</a> group:<math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M:=b_{1}(G,t):=\operatorname {rank} H_{1}(G,t),}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M:=b_{1}(G,t):=\operatorname {rank} H_{1}(G,t),}</annotation>

</semantics>

</math>

which is read as "the rank of the first <a href="Homology_(mathematics)" title="Homology (mathematics)">homology</a> group of the graph G relative to the <a href="Tree_(data_structure)" class="mw-redirect" title="Tree (data structure)">terminal nodes</a> t". This is a technical way of saying "the number of linearly independent paths through the flow graph from an entry to an exit", where:

<ul><li>"linearly independent" corresponds to homology, and backtracking is not double-counted;</li>

<li>"paths" corresponds to first homology (a path is a one-dimensional object); and</li>

<li>"relative" means the path must begin and end at an entry (or exit) point.</li></ul>

This cyclomatic complexity can be calculated. It may also be computed via absolute <a href="Betti_number" title="Betti number">Betti number</a> by identifying the terminal nodes on a given component, or drawing paths connecting the exits to the entrance. The new, augmented graph <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tilde {G}}}">

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\tilde {G}}}</annotation>

</semantics>

</math><img src="./312d458e93142c5d455e0ab9837b52147ff843dc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.676ex;" alt="{\displaystyle {\tilde {G}}}" loading="lazy"> obtains

<msub>

</mrow>

</msub>

<mover>

</mover>

</mrow>

<msub>

</mrow>

</msub>

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M=b_{1}({\tilde {G}})=\operatorname {rank} H_{1}({\tilde {G}}).}</annotation>

</semantics>

</math>

It can also be computed via <a href="Homotopy" title="Homotopy">homotopy</a>. If a (connected) control-flow graph is considered a one-dimensional <a href="CW_complex" title="CW complex">CW complex</a> called <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy">, the <a href="Fundamental_group" title="Fundamental group">fundamental group</a> of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"> will be <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \pi _{1}(X)\cong \mathbb {Z} ^{*n}}">

<msub>

</mrow>

</msub>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \pi _{1}(X)\cong \mathbb {Z} ^{*n}}</annotation>

</semantics>

</math><img src="./24b1123607d02ac07c5603513a8bfaaa08476065.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.858ex; height:2.843ex;" alt="{\displaystyle \pi _{1}(X)\cong \mathbb {Z} ^{*n}}" loading="lazy">. The value of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n+1}</annotation>

</semantics>

</math><img src="./2a135e65a42f2d73cccbfc4569523996ca0036f1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.398ex; height:2.343ex;" alt="{\displaystyle n+1}" loading="lazy"> is the cyclomatic complexity. The fundamental group counts how many loops there are through the graph up to homotopy, aligning as expected.

<div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Limiting_complexity_during_development">Limiting complexity during development</h3></div>

One of McCabe's original applications was to limit the complexity of routines during program development. He recommended that programmers should count the complexity of the modules they are developing, and split them into smaller modules whenever the cyclomatic complexity of the module exceeded 10.<a href="#cite_note-mccabe76-2">[2]</a> This practice was adopted by the <a href="NIST" class="mw-redirect" title="NIST">NIST</a> Structured Testing methodology, which observed that since McCabe's original publication, the figure of 10 had received substantial corroborating evidence. However, it also noted that in some circumstances it may be appropriate to relax the restriction and permit modules with a complexity as high as 15. As the methodology acknowledged that there were occasional reasons for going beyond the agreed-upon limit, it phrased its recommendation as "For each module, either limit cyclomatic complexity to [the agreed-upon limit] or provide a written explanation of why the limit was exceeded."<a href="#cite_note-nist-9">[9]</a>

<div class="mw-heading mw-heading3"><h3 id="Measuring_the_"structuredness"_of_a_program">Measuring the "structuredness" of a program</h3></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Essential_complexity_(numerical_measure_of_%22structuredness%22)" class="mw-redirect" title="Essential complexity (numerical measure of "structuredness")">Essential complexity (numerical measure of "structuredness")</a></div>

Section VI of McCabe's 1976 paper is concerned with determining what the control-flow graphs (CFGs) of non-<a href="Structured_programming" title="Structured programming">structured programs</a> look like in terms of their subgraphs, which McCabe identified. (For details, see <a href="Structured_program_theorem" title="Structured program theorem">structured program theorem</a>.) McCabe concluded that section by proposing a numerical measure of how close to the structured programming ideal a given program is, i.e. its "structuredness". McCabe called the measure he devised for this purpose <a href="Essential_complexity_(numerical_measure_of_%22structuredness%22)" class="mw-redirect" title="Essential complexity (numerical measure of "structuredness")">essential complexity</a>.<a href="#cite_note-mccabe76-2">[2]</a>

To calculate this measure, the original CFG is iteratively reduced by identifying subgraphs that have a single-entry and a single-exit point, which are then replaced by a single node. This reduction corresponds to what a human would do if they extracted a subroutine from the larger piece of code. (Nowadays such a process would fall under the umbrella term of <a href="Refactoring" class="mw-redirect" title="Refactoring">refactoring</a>.) McCabe's reduction method was later called condensation in some textbooks, because it was seen as a generalization of the <a href="Condensation_(graph_theory)" class="mw-redirect" title="Condensation (graph theory)">condensation to components used in graph theory</a>.<a href="#cite_note-10">[10]</a> If a program is structured, then McCabe's reduction/condensation process reduces it to a single CFG node. In contrast, if the program is not structured, the iterative process will identify the irreducible part. The essential complexity measure defined by McCabe is simply the cyclomatic complexity of this irreducible graph, so it will be precisely 1 for all structured programs, but greater than one for non-structured programs.<a href="#cite_note-nist-9">[9]</a>: 80

<div class="mw-heading mw-heading3"><h3 id="Implications_for_software_testing">Implications for software testing</h3></div>

Another application of cyclomatic complexity is in determining the number of test cases that are necessary to achieve thorough test coverage of a particular module.

It is useful because of two properties of the cyclomatic complexity, M, for a specific module:

<ul><li>M is an upper bound for the number of test cases that are necessary to achieve a complete <a href="Branch_coverage" class="mw-redirect" title="Branch coverage">branch coverage</a>.</li>

<li>M is a lower bound for the number of paths through the control-flow graph (CFG). Assuming each test case takes one path, the number of cases needed to achieve <a href="Path_coverage" class="mw-redirect" title="Path coverage">path coverage</a> is equal to the number of paths that can actually be taken. But some paths may be impossible, so although the number of paths through the CFG is clearly an upper bound on the number of test cases needed for path coverage, this latter number (of possible paths) is sometimes less than M.</li></ul>

All three of the above numbers may be equal: branch coverage <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \leq }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \leq }</annotation>

</semantics>

</math><img src="./440568a09c3bfdf0e1278bfa79eb137c04e94035.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:1.808ex; height:2.176ex;" alt="{\displaystyle \leq }" loading="lazy"> cyclomatic complexity <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \leq }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \leq }</annotation>

</semantics>

For example, consider a program that consists of two sequential if-then-else statements.

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>if (c1())

f1();

else

f2();

if (c2())

f3();

else

f4();

</pre></div>

In this example, two test cases are sufficient to achieve a complete branch coverage, while four are necessary for complete path coverage. The cyclomatic complexity of the program is 3 (as the strongly connected graph for the program contains 8 edges, 7 nodes, and 1 connected component) (8 − 7 + 2).

In general, in order to fully test a module, all execution paths through the module should be exercised. This implies a module with a high complexity number requires more testing effort than a module with a lower value since the higher complexity number indicates more pathways through the code. This also implies that a module with higher complexity is more difficult to understand since the programmer must understand the different pathways and the results of those pathways.

Unfortunately, it is not always practical to test all possible paths through a program. Considering the example above, each time an additional if-then-else statement is added, the number of possible paths grows by a factor of 2. As the program grows in this fashion, it quickly reaches the point where testing all of the paths becomes impractical.

One common testing strategy, espoused for example by the NIST Structured Testing methodology, is to use the cyclomatic complexity of a module to determine the number of <a href="White-box_testing" title="White-box testing">white-box tests</a> that are required to obtain sufficient coverage of the module. In almost all cases, according to such a methodology, a module should have at least as many tests as its cyclomatic complexity. In most cases, this number of tests is adequate to exercise all the relevant paths of the function.<a href="#cite_note-nist-9">[9]</a>

As an example of a function that requires more than mere branch coverage to test accurately, reconsider the above function. However, assume that to avoid a bug occurring, any code that calls either <code>f1()</code> or <code>f3()</code> must also call the other.<a href="#cite_note-11">[a]</a> Assuming that the results of <code>c1()</code> and <code>c2()</code> are independent, the function as presented above contains a bug. Branch coverage allows the method to be tested with just two tests, such as the following test cases:

<ul><li><code>c1()</code> returns true and <code>c2()</code> returns true</li>

<li><code>c1()</code> returns false and <code>c2()</code> returns false</li></ul>

Neither of these cases exposes the bug. If, however, we use cyclomatic complexity to indicate the number of tests we require, the number increases to 3. We must therefore test one of the following paths:

<ul><li><code>c1()</code> returns true and <code>c2()</code> returns false</li>

<li><code>c1()</code> returns false and <code>c2()</code> returns true</li></ul>

Either of these tests will expose the bug.

<div class="mw-heading mw-heading3"><h3 id="Correlation_to_number_of_defects">Correlation to number of defects</h3></div>

Multiple studies have investigated the correlation between McCabe's cyclomatic complexity number with the frequency of defects occurring in a function or method.<a href="#cite_note-fenton-12">[11]</a> Some studies<a href="#cite_note-schroeder99-13">[12]</a> find a positive correlation between cyclomatic complexity and defects; functions and methods that have the highest complexity tend to also contain the most defects. However, the correlation between cyclomatic complexity and program size (typically measured in <a href="Lines_of_code" class="mw-redirect" title="Lines of code">lines of code</a>) has been demonstrated many times. <a href="Les_Hatton" title="Les Hatton">Les Hatton</a> has claimed<a href="#cite_note-taic-14">[13]</a> that complexity has the same predictive ability as lines of code.

Studies that controlled for program size (i.e., comparing modules that have different complexities but similar size) are generally less conclusive, with many finding no significant correlation, while others do find correlation. Some researchers question the validity of the methods used by the studies finding no correlation.<a href="#cite_note-kan-15">[14]</a> Although this relation likely exists, it is not easily used in practice.<a href="#cite_note-cherf-16">[15]</a> Since program size is not a controllable feature of commercial software, the usefulness of McCabe's number has been questioned.<a href="#cite_note-fenton-12">[11]</a> The essence of this observation is that larger programs tend to be more complex and to have more defects. Reducing the cyclomatic complexity of code is <a href="Correlation_does_not_imply_causation" title="Correlation does not imply causation">not proven</a> to reduce the number of errors or bugs in that code. International safety standards like <a href="ISO_26262" title="ISO 26262">ISO 26262</a>, however, mandate coding guidelines that enforce low code complexity.<a href="#cite_note-ISO26262Part3-17">[16]</a>

<ul><li><a href="Programming_complexity" title="Programming complexity">Programming complexity</a></li>

<li><a href="Complexity_trap" class="mw-redirect" title="Complexity trap">Complexity trap</a></li>

<li><a href="Computer_program" title="Computer program">Computer program</a></li>

<li><a href="Computer_programming" title="Computer programming">Computer programming</a></li>

<li><a href="Control_flow" title="Control flow">Control flow</a></li>

<li><a href="Decision-to-decision_path" title="Decision-to-decision path">Decision-to-decision path</a></li>

<li><a href="Design_predicates" title="Design predicates">Design predicates</a></li>

<li><a href="Essential_complexity_(numerical_measure_of_%22structuredness%22)" class="mw-redirect" title="Essential complexity (numerical measure of "structuredness")">Essential complexity (numerical measure of "structuredness")</a></li>

<li><a href="Halstead_complexity_measures" title="Halstead complexity measures">Halstead complexity measures</a></li>

<li><a href="Software_engineering" title="Software engineering">Software engineering</a></li>

<li><a href="Software_testing" title="Software testing">Software testing</a></li>

<li><a href="Static_program_analysis" title="Static program analysis">Static program analysis</a></li>

<li><a href="Maintainability" title="Maintainability">Maintainability</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist reflist-lower-alpha">

<li id="cite_note-11"><a href="#cite_ref-11">^</a> This is a fairly common type of condition; consider the possibility that <code>f1</code> allocates some resource which <code>f3</code> releases.

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFA_J_Sobey" class="citation web cs1">A J Sobey. <a rel="nofollow" class="external text" href="http://users.csc.calpoly.edu/~jdalbey/206/Lectures/BasisPathTutorial/index.html">"Basis Path Testing"</a>.</cite>

</li>

<li id="cite_note-mccabe76-2">^ <a href="#cite_ref-mccabe76_2-0">a</a> <a href="#cite_ref-mccabe76_2-1">b</a> <a href="#cite_ref-mccabe76_2-2">c</a> <a href="#cite_ref-mccabe76_2-3">d</a> <a href="#cite_ref-mccabe76_2-4">e</a> <cite id="CITEREFMcCabe1976" class="citation journal cs1">McCabe (December 1976). "A Complexity Measure". IEEE Transactions on Software Engineering. SE-2 (4): 308–320. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2Ftse.1976.233837">10.1109/tse.1976.233837</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:9116234">9116234</a>.</cite>

</li>

<li id="cite_note-Laplante2007-3"><a href="#cite_ref-Laplante2007_3-0">^</a> <cite id="CITEREFPhilip_A._Laplante2007" class="citation book cs1">Philip A. Laplante (25 April 2007). What Every Engineer Should Know about Software Engineering. CRC Press. p. 176. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4200-0674-2</bdi>.</cite>

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite id="CITEREFFricker2018" class="citation web cs1">Fricker, Sébastien (April 2018). <a rel="nofollow" class="external text" href="https://www.froglogic.com/blog/tip-of-the-week/what-is-cyclomatic-complexity/">"What exactly is cyclomatic complexity?"</a>. froglogic GmbH. Retrieved October 27, 2018. <q>To compute a graph representation of code, we can simply disassemble its assembly code and create a graph following the rules: ...</q></cite>

</li>

<li id="cite_note-ecst-5">^ <a href="#cite_ref-ecst_5-0">a</a> <a href="#cite_ref-ecst_5-1">b</a> <cite id="CITEREFJ._BelzerA._KentA._G._HolzmanJ._G._Williams1992" class="citation book cs1">J. Belzer; A. Kent; A. G. Holzman; J. G. Williams (1992). Encyclopedia of Computer Science and Technology. CRC Press. pp. 367–368.</cite>

</li>

<li id="cite_note-harrison-6"><a href="#cite_ref-harrison_6-0">^</a> <cite id="CITEREFHarrison1984" class="citation journal cs1">Harrison (October 1984). "Applying Mccabe's complexity measure to multiple-exit programs". Software: Practice and Experience. 14 (10): 1004–1007. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1002%2Fspe.4380141009">10.1002/spe.4380141009</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:62422337">62422337</a>.</cite>

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <cite id="CITEREFThomas_McCabe_Jr.2008" class="citation web cs1">Thomas McCabe Jr. (2008). <a rel="nofollow" class="external text" href="http://www.mccabe.com/ppt/SoftwareQualityMetricsToIdentifyRisk.ppt">"Software Quality Metrics to Identify Risk"</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20220329072759/http://www.mccabe.com/ppt/SoftwareQualityMetricsToIdentifyRisk.ppt">Archived</a> from the original on 2022-03-29.</cite>

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <cite id="CITEREFDiestel2000" class="citation book cs1">Diestel, Reinhard (2000). Graph theory. Graduate texts in mathematics 173 (2 ed.). New York: Springer. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-387-98976-1</bdi>.</cite>

</li>

<li id="cite_note-nist-9">^ <a href="#cite_ref-nist_9-0">a</a> <a href="#cite_ref-nist_9-1">b</a> <a href="#cite_ref-nist_9-2">c</a> <cite id="CITEREFArthur_H._WatsonThomas_J._McCabe1996" class="citation web cs1">Arthur H. Watson; Thomas J. McCabe (1996). <a rel="nofollow" class="external text" href="http://www.mccabe.com/pdf/mccabe-nist235r.pdf">"Structured Testing: A Testing Methodology Using the Cyclomatic Complexity Metric"</a> (PDF). NIST Special Publication 500-235.</cite>

</li>

<li id="cite_note-10"><a href="#cite_ref-10">^</a> <cite id="CITEREFPaul_C._Jorgensen2002" class="citation book cs1">Paul C. Jorgensen (2002). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=Yph_AwAAQBAJ&pg=PA150">Software Testing: A Craftsman's Approach, Second Edition</a> (2nd ed.). CRC Press. pp. 150–153. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-8493-0809-3</bdi>.</cite>

</li>

<li id="cite_note-fenton-12">^ <a href="#cite_ref-fenton_12-0">a</a> <a href="#cite_ref-fenton_12-1">b</a> <cite id="CITEREFNorman_E_FentonMartin_Neil1999" class="citation journal cs1">Norman E Fenton; Martin Neil (1999). <a rel="nofollow" class="external text" href="http://www.eecs.qmul.ac.uk/~norman/papers/defects_prediction_preprint105579.pdf">"A Critique of Software Defect Prediction Models"</a> (PDF). IEEE Transactions on Software Engineering. 25 (3): 675–689. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.548.2998">10.1.1.548.2998</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2F32.815326">10.1109/32.815326</a>.</cite>

</li>

<li id="cite_note-schroeder99-13"><a href="#cite_ref-schroeder99_13-0">^</a> <cite id="CITEREFSchroeder,_Mark1999" class="citation journal cs1">Schroeder, Mark (1999). "A Practical guide to object-oriented metrics". IT Professional. 1 (6): 30–36. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2F6294.806902">10.1109/6294.806902</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:14945518">14945518</a>.</cite>

</li>

<cite id="CITEREFLes_Hatton2008" class="citation web cs1">Les Hatton (2008). <a rel="nofollow" class="external text" href="http://www.leshatton.org/TAIC2008-29-08-2008.html">"The role of empiricism in improving the reliability of future software"</a>. version 1.1.</cite>

</li>

<cite id="CITEREFKan2003" class="citation book cs1">Kan (2003). Metrics and Models in Software Quality Engineering. Addison-Wesley. pp. 316–317. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-201-72915-3</bdi>.</cite>

</li>

<li id="cite_note-cherf-16"><a href="#cite_ref-cherf_16-0">^</a> <cite id="CITEREFG.S._Cherf1992" class="citation journal cs1">G.S. Cherf (1992). "An Investigation of the Maintenance and Support Characteristics of Commercial Software". Journal of Software Quality. 1 (3): 147–158. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fbf01720922">10.1007/bf01720922</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1573-1367">1573-1367</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:37274091">37274091</a>.</cite>

</li>

<li id="cite_note-ISO26262Part3-17"><a href="#cite_ref-ISO26262Part3_17-0">^</a> <cite class="citation book cs1"><a rel="nofollow" class="external text" href="https://www.iso.org/obp/ui/#iso:std:iso:26262:-3:ed-1:v1:en">ISO 26262-3:2011(en) Road vehicles — Functional safety — Part 3: Concept phase</a>. International Standardization Organization.</cite>

</li>

</ol></div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://www.mathworks.com/discovery/cyclomatic-complexity.html">Generating cyclomatic complexity metrics with Polyspace</a></li>

<li><a rel="nofollow" class="external text" href="http://www.leshatton.org/Documents/TAIC2008-29-08-2008.pdf">The role of empiricism in improving the reliability of future software</a></li>

<li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20230203195937/https://www.cqse.eu/en/news/blog/mccabe-cyclomatic-complexity//">McCabe's Cyclomatic Complexity and Why We Don't Use It</a></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-03-10" href="https://en.wikipedia.org/wiki/?title=Cyclomatic_complexity&oldid=1279841720">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>